import random
from random import randint, choice, shuffle


# 单元格类型
# 0 - 路，1 - 墙
class CellType:
    ROAD = 0
    WALL = 1

    def __init__(self, type, loc=None, pre=None):
        # 根据不同类型上色
        self.type = type
        # 标记上一个节点
        self.pre = pre
        # 当前节点坐标
        self.loc = loc
        # 是否被遍历(正向)
        self.isvisited = False
        # 是否被遍历(逆向)
        self.isvisitedl = False
        # 距离起点步数(正向)
        self.step = 0
        # 距离终点步数(逆向)
        self.stepl = 0
        # 是否是终点
        self.isend = False
        # 被访问的次数
        self.visited_num = 0


# 墙的方向
class Direction:
    LEFT = 0,
    UP = 1,
    RIGHT = 2,
    DOWN = 3,


# 迷宫地图
class Maze:

    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.maze = [[0 for x in range(self.width)] for y in range(self.height)]
        self.cellMaze = []

    def reset_cellMaze(self, maze=None):
        if maze is None:
            self.cellMaze = []
            for i in range(len(self.maze)):
                tmp = []
                for j in range(len(self.maze[i])):
                    tmp.append(CellType(type=1 if self.maze[i][j] == 1 else 0, loc=[i, j]))
                self.cellMaze.append(tmp)
        else:
            self.cellMaze = []
            for i in range(len(self.maze)):
                tmp = []
                for j in range(len(self.maze[i])):
                    tmp.append(CellType(type=1 if maze[i][j] == 1 else 0, loc=[i, j]))
                self.cellMaze.append(tmp)

    def reset_maze(self, value):
        for y in range(self.height):
            for x in range(self.width):
                self.set_maze(x, y, value)

    def set_maze(self, x, y, value):
        self.maze[y][x] = CellType.ROAD if value == CellType.ROAD else CellType.WALL

    def visited(self, x, y):
        return self.maze[y][x] != 1


def check_neighbors(maze, begin, x, y, width, height, checklist):
    bx, by = begin
    directions = []
    if x > bx:
        if not maze.visited(2 * (x - 1) + 1, 2 * y + 1):
            directions.append(Direction.LEFT)
    if y > by:
        if not maze.visited(2 * x + 1, 2 * (y - 1) + 1):
            directions.append(Direction.UP)
    if x < width - 1:
        if not maze.visited(2 * (x + 1) + 1, 2 * y + 1):
            directions.append(Direction.RIGHT)
    if y < height - 1:
        if not maze.visited(2 * x + 1, 2 * (y + 1) + 1):
            directions.append(Direction.DOWN)
    if len(directions):
        direction = choice(directions)
        if direction == Direction.LEFT:
            maze.set_maze(2 * (x - 1) + 1, 2 * y + 1, CellType.ROAD)
            maze.set_maze(2 * x, 2 * y + 1, CellType.ROAD)
            checklist.append((x - 1, y))
        elif direction == Direction.UP:
            maze.set_maze(2 * x + 1, 2 * (y - 1) + 1, CellType.ROAD)
            maze.set_maze(2 * x + 1, 2 * y, CellType.ROAD)
            checklist.append((x, y - 1))
        elif direction == Direction.RIGHT:
            maze.set_maze(2 * (x + 1) + 1, 2 * y + 1, CellType.ROAD)
            maze.set_maze(2 * x + 2, 2 * y + 1, CellType.ROAD)
            checklist.append((x + 1, y))
        elif direction == Direction.DOWN:
            maze.set_maze(2 * x + 1, 2 * (y + 1) + 1, CellType.ROAD)
            maze.set_maze(2 * x + 1, 2 * y + 2, CellType.ROAD)
            checklist.append((x, y + 1))
        return True
    return False


def random_prime(map, begin, width, height):
    x, y = begin
    start_x, start_y = (randint(x, (width - 1) // 2 - 1), randint(y, (height - 1) // 2 - 1))
    print(start_x, start_y)
    map.set_maze(2 * start_x + 1, 2 * start_y + 1, CellType.ROAD)
    checklist = [(start_x, start_y)]
    while len(checklist):
        entry = choice(checklist)
        if not check_neighbors(map, begin, entry[0], entry[1], (width - 1) // 2, (height - 1) // 2, checklist):
            checklist.remove(entry)


def do_random_prime(map, begin, width, height):
    # map.reset_maze(CellType.WALL)
    random_prime(map, begin, width, height)


def set_entrance_exit(maze):
    entrance = []
    for i in range(maze.height):
        if maze.maze[i][1] == 0:
            maze.set_maze(0, i, 0)
            entrance = [i, 0]
            break
    exit = []
    for i in range(maze.height - 1, 0, -1):
        if maze.maze[i][maze.width - 2] == 0:
            maze.set_maze(maze.width - 1, i, 0)
            exit = [i, maze.width - 1]
            break
    return entrance, exit


def random_dfs(start, begin, end, maze, dfs, direction, operation):
    x, y = start
    bx, by = begin
    ex, ey = end
    dfs[y][x] = 1
    shuffle(direction)
    for d in direction:
        px, py = (x + y for x, y in zip(start, operation[d]))
        if px < bx or px >= ex or py < by or py >= ey:
            pass
        else:
            if dfs[py][px] != 1:
                mx = 2 * x + 1
                my = 2 * y + 1
                if d == 1:
                    maze.set_maze(mx, my - 1, CellType.ROAD)
                elif d == 2:
                    maze.set_maze(mx, my + 1, CellType.ROAD)
                elif d == 3:
                    maze.set_maze(mx - 1, my, CellType.ROAD)
                elif d == 4:
                    maze.set_maze(mx + 1, my, CellType.ROAD)
                random_dfs((px, py), (bx, by), end,
                           maze, dfs, direction, operation)


def do_random_dfs(map, begin, end, dfs):
    direction = [1, 2, 3, 4]
    operation = {1: (0, -1), 2: (0, 1), 3: (-1, 0), 4: (1, 0)}
    random_dfs(begin, begin, end, map, dfs, direction, operation)


def generate_maze(width=21, height=21):
    # 初始化迷宫
    # maze = Maze(121, 121)
    maze = Maze(width, height)
    # 生成地图,每种算法各生成二分之一的地图
    # 深度优先算法
    import sys
    sys.setrecursionlimit(10000)
    for i in range(maze.width):
        if i % 2 == 0:
            for j in range(maze.width):
                maze.set_maze(j, i, CellType.WALL)
    for i in range(maze.height):
        if i % 2 == 0:
            for j in range(maze.height):
                maze.set_maze(i, j, CellType.WALL)
    ex = (maze.width - 1) // 2
    mx = (ex) // 2
    ey = (maze.height - 1) // 2
    my = (ey) // 2
    dfs = [[0 for col in range((maze.width - 1) // 2)] for row in range((maze.height - 1) // 2)]
    # do_random_dfs(maze, (0, 0), ((maze.width - 1) // 2, (maze.height - 1) // 2), dfs)
    # do_random_dfs(maze, (0, my), (mx, ey), dfs)
    # do_random_dfs(maze, (mx, 0), (ex, my), dfs)
    do_random_dfs(maze, (0, 0), (mx, my), dfs)
    do_random_dfs(maze, (mx, my), (ex, ey), dfs)
    # do_random_prime(maze)

    # prime算法
    for i in range(ex):
        for j in range(ey + 1, maze.height):
            maze.set_maze(i, j, CellType.WALL)
    for m in range(ex + 1, maze.width):
        for n in range(ey):
            maze.set_maze(m, n, CellType.WALL)

    do_random_prime(maze, (0, my), ex + 1, maze.height)
    # do_random_prime(maze, (0, 0), ex + 1, ey + 1)
    do_random_prime(maze, (mx, 0), maze.width, ey + 1)
    # do_random_prime(maze, (mx, my), maze.width, maze.height)
    choice_dict = {'l': (1, ex), 'r': (ex + 1, maze.width - 1), 'u': (1, ey), 'd': (ey + 1, maze.height - 1)}
    choice_list = ['l', 'r', 'u', 'd']
    b = random.choice(choice_list)
    choice_dict[b] = False
    for k, v in choice_dict.items():
        if not v:
            continue
        if k == 'l' or k == 'r':
            maze.set_maze(ey, random.randrange(*v, 2), CellType.ROAD)
        else:
            maze.set_maze(random.randrange(*v, 2), ex, CellType.ROAD)

    # for i in maze.maze:
    #     print(i)
    # raise

    # 选择起点和终点
    maze_entrance, maze_exit = set_entrance_exit(maze)
    maze.reset_cellMaze()
    # 返回地图
    return maze, maze_entrance, maze_exit
